Last but not least, we will have a look at another approach to two-dimensional languages. Known from the string languages, we can introduce regular expressions. These are defined recursively as follows. This definition is from  \cite{giammarresi1997twodimensional}.

\begin{compactitem}
	\item Let $a \in \Sigma$ be a letter. Then $a$ is a regular expression. Furthermore, the empty letter $\emptyset$ is a regular expression. 
	\item Let $\alpha$ and $\beta$ be two regular expressions. Then
	
	\begin{compactitem}
		\item $(\alpha) \cap (\beta)$,
		\item $(\alpha) \cup (\beta)$,
		\item $^\mathsf{c}(\alpha)$,
		\item $(\alpha) \hcat (\beta)$,
		\item $(\alpha) \vcat (\beta)$,
		\item $(\alpha)^{*\hcat}$ and
		\item $(\alpha)^{*\vcat}$
	\end{compactitem}
	
	are regular expressions. 
\end{compactitem} 

For every regular expression $\alpha$, $L(\alpha)$ is the language corresponding to the regular expression. $L(\emptyset) = \{\}$ is the language containing zero pictures. A single character $a \in \Sigma$ generates the language $L(a) = \{\begin{tabular}{|c|}
	\hline
	a \\
	\hline
	\end{tabular}\}$. $L((\alpha) \cap (\beta)) = L(\alpha) \cap L(\beta)$, $L((\alpha) \cup (\beta)) = \{L(\alpha) \cup L(\beta)\}$, $L((\alpha) \hcat (\beta)) = L(\alpha) \hcat L(\beta)$ and $L((\alpha) \vcat (\beta)) = L(\alpha) \vcat L(\beta)$ are intersection, union, horizontal and vertical concatenation. Moreover, $(\alpha)^{*\hcat} = L(\alpha)^{*\hcat}$ and $(\alpha)^{*\vcat} = L(\alpha)^{*\vcat}$ are the reflexive, transitive closures of $\hcat$ and $\vcat$. $^\mathsf{c}(\alpha) = \Sigma^{*,*} \setminus L(\alpha)$ describes the complement of the language generated by $\alpha$. 

The family of languages generated by regular expressions is denoted by $\familyOf{RE}$. 

\begin{example}
	Let $\alpha = (((a \ominus b)^{*\ominus})\rotatebox{90}{$\ominus$}((b \ominus a)^{*\ominus}))^{*\rotatebox{90}{$\ominus$}}$ be a regular expression over the alphabet $\{a, b\}$. The language $L(\alpha)$ generated by this regular expression is containing "chessboard" pictures of a's and b's of even side-length. The following picture is in $L(\alpha)$: 
	
	\begin{center}
		\begin{tabular}{|c|c|c|c|c|c|}
			\hline
			a & b & a & b & a & b\\
			\hline
			b & a & b & a & b & a\\
			\hline
			a & b & a & b & a & b\\
			\hline
			b & a & b & a & b & a\\
			\hline
		\end{tabular}
	\end{center}
\end{example}

A close look to the regular expressions reveals that it is impossible to generate square picture with one character whereas the class REC is able to. In~\cite{matz1997regular}, O. Matz proposes some new operations to overcome this problem. If we use some smaller sets of regular expressions, we will see that it exits a class that coincide with the hv-local languages. 

\begin{definition}
	Let $R_1 = \{\ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \cup, \cap\}$ and $R_2 = \{\ominus, \rotatebox{90}{$\ominus$}, \cup, \cap, ^c\}$ be two subsets of regular expressions. The classes of languages generated by $R_1$ and $R_2$ are denoted by $\familyOf{CFRE}$ and $\familyOf{SFRE}$ are called complement-free regular expressions and star-free regular expressions respectively. 
\end{definition}

If we use projection on complement-free regular expressions we speak about the class $\familyOf{PCFRE}$ of projected complement-free regular expressions. 

\begin{theorem}
	The family of hv-local languages is properly included in $\familyOf{CFRE}$. 
\end{theorem}

This theorem can be proved by separating the dominos $\Delta$ in horizontal and vertical dominos ($\Delta_h$ and $\Delta_v$). These two sets can be generated by regular expressions $r_h$ and $r_v$. The language $L(\Delta)$ is then generated by $L((r_h)^{*\vcat}) \cap (r_v)^{*\hcat})$. A detailed proof can be found in~\cite{giammarresi1997twodimensional}. 

\begin{theorem}
	$REC = \familyOf{PCFRE}$. 
\end{theorem}

The first direction can be shown because we know that for every language $L \in$
REC there exists a hv-local language $K$ and a projection $\pi$, such that $L =
\pi(K)$. Since every hv-local language can be generated by a CFRE, this
direction is clear. The way back can be shown because the atomic languages belong to REC and REC is closed under the operations of the regular expressions. More about that in~\cite{giammarresi1997twodimensional}.

\begin{theorem}
	$\familyOf{CFRE} \subset$ REC. 
\end{theorem}

As an example, the language which consists of square shaped pictures over a one letter alphabet is in REC, but is not in $\familyOf{CFRE}$. Furthermore, neither $\familyOf{SFRE}$ nor $\familyOf{RE}$ does coincide with REC. 

In~\cite{matz2007recognizable} Matz introduces another set of regular expressions: $R_3 = \{\ominus, \rotatebox{90}{$\ominus$}, *\ominus, *\rotatebox{90}{$\ominus$}, \cup\}$. The class of languages generated by this set he called REG. 

\begin{theorem}
	REG is closed under: 

	\begin{compactitem}
		\item union,
		\item row and column concatenation and closure and
		\item projection.
	\end{compactitem}
\end{theorem}

This is proved in~\cite{matz2007recognizable}. Matz was also able to show, that the membership and emptiness problems of REG are decidable in polynomial time. Moreover, he was able to position the language in a hierarchy of regular expressions.

\begin{theorem}
	$REG \subset \familyOf{CFRE} \subset REC$
\end{theorem}

Furthermore, he claims that REG is the better candidate for ``regular'' picture languages than REC. This statement is based on the fact, that the languages in REC are as ``complex'' as context-free string languages. 